선택정렬,이중선택정렬에 대해서 알아보자! feat.JavaScript

Selection Sort(선택정렬)

선택정렬은 제자리 정렬 알고리즘입니다. 제자리 정렬이란 메모리를 추가로

거의 사용하지 않는 알고리즘을 의미합니다. 또한 불안정 정렬인데 불안정 정렬은

정렬 전 동일한 키값의 요소 순서가 정렬 후 유지 안 되는 알고리즘을 불안정 정렬이라고 합니다.

[3, 2, 1, 5¹, 7, 5²] 배열이 있습니다.

이를 오름차순으로 정렬한다고 할 때

[1, 2, 3, 5¹, 5², 7]이 된다면 안정 정렬

[1, 2, 3, 5², 5¹, 7]이 될 수 있다면 불안정 정렬입니다.

선택 정렬은 다음과 같은 순서로 이루어집니다.

1. 주어진 리스트 중에 최솟값을 찾습니다.

2. 그 값을 맨 앞에 위치한 값과 교체합니다.

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체합니다.

선택 정렬을 나타낸 애니메이션이 있는데 최솟값이 하나씩 붙는 모습이 재밌습니다(?)

최선, 최악, 평균 시간복잡도는 O(N²)로 동일합니다. 공간복잡도는 제자리 정렬답게 O(1)이죠

구현 코드

const N = 6;
let data = [3, 5, 6, 7, 2, 1];

for (let i = 0; i < N; i++) {
  let minIndex = i;
  for (let j = i + 1; j < N; j++) {
    if (data[minIndex] > data[j]) {
      minIndex = j;
    }
  }
  if (minIndex !== i) {
    let temp = data[minIndex];
    data[minIndex] = data[i];
    data[i] = temp;
  }
}
console.log(data);

맨 앞의 값을 가지고 뒤에 값들과 비교해서 하나라도 더 작은 값이 있다면 작은 값의 index를 기억합니다

끝까지 검사했을 때 작은 값의 index를 하나라도 찾았다면 위치를 바꿔줍니다.

이중 선택 정렬

기존의 선택 정렬에서 더 업그레이드된 알고리즘입니다.

루틴을 돌면서 최댓값과 최솟값을 모두 찾습니다. 최솟값은 1번쨰와 바꾸고 최댓값은 끝과 바꾼 다음

루틴을 도는 범위를 양쪽으로 한 칸씩 줄여서 반복하는 방식을 사용합니다.

탐색 횟수가 절반으로 줄어들게 됩니다.

이중 선택 정렬 구현

function doubleSelection(start, end) {
  while (start < end) {
    let min = start;
    let max = end;

    for (let i = start + 1; i < end; i++) {
      if (data[i] < data[min]) {
        min = i;
      }
      if (data[i] > data[max]) {
        max = i;
      }
    }

    if (start !== min) {
      let temp = data[start];
      data[start] = data[min];
      data[min] = temp;
    }

    if (end !== max) {
      let temp = data[end];
      data[end] = data[max];
      data[max] = temp;
    }

    start++;
    end--;
    console.log(data, min, max);
  }
}

const N = 6;
let data = [3, 5, 6, 7, 2, 1];

doubleSelection(0, N);

console.log(data);

부끄럽지만 위의 코드는 이중 선택정렬을 실패한 코드이다. 어느 정도는 동작을 하지만

완전하게 동작하지는 않는다 해결 방법을 아시는 분은 댓글을 부탁드립니다. ㅠㅠ